package day1_array.leetcode;

/**
 * 两数之和问题
 * @Author: yuisama
 * @Date: 2022/3/29 17:58
 * @Description:
 */
public class Num167_TwoSum {
    // 二分查找法 nlogn
//    public int[] twoSum(int[] numbers, int target) {
//        for (int i = 0; i < numbers.length; i++) {
//            int j = binerySearch(numbers,i + 1,numbers.length - 1,target - numbers[i]);
//            if (j != -1) {
//                return new int[] {i + 1,j + 1};
//            }
//        }
//        return new int[0];
//    }
//
//    public int binerySearch(int[] arr,int l,int r,int target) {
//        while (l <= r) {
//            int mid = l + ((r - l) >> 1);
//            if (target > arr[mid]) {
//                l = mid + 1;
//            }else if (target < arr[mid]) {
//                r = mid - 1;
//            }else {
//                return mid;
//            }
//        }
//        return -1;
//    }
    // 对撞指针O(n)
    public int[] twoSum(int[] numbers, int target) {
        assert numbers.length >= 2;
        int l = 0;
        int r = numbers.length - 1;
        while (l < r) {
            if (numbers[l] + numbers[r] == target) {
                return new int[] {l + 1,r + 1};
            }else if (numbers[l] + numbers[r] < target) {
                l ++;
            }else {
                r --;
            }
        }
        throw new RuntimeException("No Solution!");
    }
}
